# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2023/3/10 9:55
@FileName      : 01背包问题方案数.py
@LastEditors   : None
@Editors       : PyCharm
"""
"""题目：2022拆分成10种不同的正整数，有多少种分法"""
# 非滚动数组
dp = [[[0] * 11 for i in range(2222)] for j in range(2222)]
for i in range(0, 2023): dp[i][0][0] = 1  # 初始化
# i是依次装入的东西，j是所有空间,k是记录装几件物品
for i in range(1, 2023):
    for j in range(1, 2023):
        for k in range(1, 11):
            if i > j:
                dp[i][j][k] = dp[i - 1][j][k]
            else:
                dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - i][k - 1]
print(dp[2022][2022][10])

# 滚动数组
dp = [[0] * 11 for i in range(2222)]
dp[0][0] = 1  # 初始化
# i是依次装入的东西，j是所有空间,k是记录装几件物品
for i in range(1, 2023):
    for j in range(2022, i - 1, -1):
        for k in range(10, 0, -1):
            dp[j][k] += dp[j - i][k - 1]
print(dp[2022][10])